#include "BinaryTreeNode.h"

BTNode *BuyNode(BTNodeType n)
{
    BTNode *newnode = (BTNode *)malloc(sizeof(BTNode));
    newnode->_data = n;
    newnode->_left = NULL;
    newnode->_right = NULL;
}

// 前序遍历
void PrevOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }

    printf("%d ", root->_data);
    PrevOrder(root->_left);
    PrevOrder(root->_right);
}

// 中序遍历
void InOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }

    InOrder(root->_left);
    printf("%d ", root->_data);
    InOrder(root->_right);
}

// 后序遍历
void PostOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }

    PostOrder(root->_left);
    PostOrder(root->_right);
    printf("%d ", root->_data);
}

// 求结点个数
size_t NodeSize(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    return 1 + NodeSize(root->_left) + NodeSize(root->_right);
}

// 求叶子结点个数
size_t LeafNodeSize(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    if (root->_left == NULL && root->_right == NULL)
    {
        return 1;
    }

    return LeafNodeSize(root->_left) + LeafNodeSize(root->_right);
}

// 求高度
size_t Height(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    size_t left = Height(root->_left);
    size_t right = Height(root->_right);

    size_t max = left > right ? left : right;
    return 1 + max;
}

//求第k层结点的个数
size_t KSize(BTNode* root,int k)
{
    if(root == NULL)
    {
        return 0;
    }
    if(k == 1)
    {
        return 1;
    }

    return KSize(root->_left,k-1)+KSize(root->_right,k-1);
}

//查找值为k的结点
BTNode* FindK(BTNode* root,int k)
{
    if(root == 0)
    {
        return 0;
    }
    if(root ->_data == k)
    {
        return root;
    }

    BTNode* find_left = FindK(root->_left,k);
    return find_left == NULL? FindK(root->_right,k):NULL;
}